#include<iostream>
#include<map>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;

// void test_set01()
// {
//     set<int> s;
//     s.insert(10);
//     s.erase(s.end());   // 删除一个不存在的迭代器会报错

//     set<int> s1 = {4,2,1,8,6,6,5,9};
//     auto it1 = s1.find(6);   // 返回迭代器，O(log n)
//     auto it2 = find(s1.begin(), s1.end(), 6); // O(n)
// }
// 删除最小值：begin
// lower_bound(x) 返回 >= x的第一个
// upper_bound(x) 返回 > x的第一个 
// multiset与set区别：
// 1.有无重复元素
// 2.multiset的find(x)返回中序遍历的第一个x

// 用途：
// 1链表判环
// 2两个数组的交集（349）

// int main()
// {
//     // test_set01();
//     const int x = 10;
//     auto& e = x;
//     cout << e;
//     return 0;
// }

// class Solution {
// public:
//     struct Less
//     {
//         bool operator()(const pair<string, int>& p1, const pair<string, int>& p2) const
//         {
//             return p1.second < p2.second || p1.second == p2.second && p1.first < p2.first;
//         }
//     };
//     vector<string> topKFrequent(vector<string> words, int k) {
//         map<string, int> cnt;
//         for(auto& s : words) cnt[s]++;
//         set<pair<string, int>, Less> q(cnt.begin(), cnt.end());
//         vector<string> res;
//         for(auto&[s, c] : q)
//         {
//             res.push_back(s);
//             if(--k == 0) break;
//         }
//         return res;
//     }
// };

// int main()
// {
//     Solution().topKFrequent({"i", "love", "leetcode", "i", "love", "coding"}, 2);
//     return 0;
// }

/********************* set ******************/

struct my_cmp
{
    // 按绝对值的顺序
    bool operator() (int a, int b) const
    {
        return abs(a) < abs(b);
    }
};
void test_set01()
{
    int a[6] = {6,-3,5,7,-9,2};
    set<int> s(a, a + 6);       // 默认升序
    set<int, greater<int>> s1(a, a + 6);    // 降序
    set<int, my_cmp> s2(a, a + 6);      // 按绝对值升序

    for(auto& e : s) cout << e << ' ';
    cout << endl;
    
    for(auto& e : s1) cout << e << ' ';
    cout << endl;
    
    for(auto& e : s2) cout << e << ' ';
    cout << endl;

    // set<int> s1;    // 默认构造
    // set<int> s2 = {4,4,4,4,2,2,2,1,8,6,5,9};  // 列表构造

    // int a[] = {6,3,5,7,9,2};
    // set<int> s3(a, a + 5);   // 迭代器区间构造

    // for(auto& e : s1) cout << e << ' ';
    // cout << endl;
    
    // for(auto& e : s2) cout << e << ' ';
    // cout << endl;
    
    // for(auto& e : s3) cout << e << ' ';
    // cout << endl;

}

void test_set02()
{
    set<int> s = { 2,3,5,6,7,9 };

    auto it = s.find(3);    // 查找元素3。找到了返回指向元素的迭代器，否则返回s.end()
    cout << *it << endl;

    it = s.lower_bound(5);  // 查找第一个 >= 5 的元素，找到了返回其迭代器，否则返回s.end();
    cout << *it << endl;

    it = s.upper_bound(5);  // 查找第一个 > 5 的元素，找到了返回其迭代器，否则返回s.end();
    cout << *it << endl;

    int cnt = s.count(4);   // 查询容器种元素4的个数。对于set而言，找到了返回1，否则返回0
    cout << cnt << endl;
    cnt = s.count(5);
    cout << cnt << endl;
}

void test_set03()
{
    set<int> s;
    int a[] = { 2,3,5,6,7,9 };
    for(auto e : a)     
        s.insert(e);    // 把a数组的所有元素插入到s种
    
    auto p = s.insert(2);    
    // insert的返回值：
    // 成功插入返回 pair<插入元素的迭代器, true>，否则返回 pair<插入元素的迭代器, false>
    cout << *(p.first) << " " << p.second << endl;

    p = s.insert(999);
    cout << *(p.first) << " " << p.second << endl;
}

void test_set04()
{
    set<int> s = { 2,3,5,6,7,9 };
    int cnt = s.erase(2);   // 删除2。
    // erase的返回值是成功删除的元素个数。对于set而言成功删除返回1，否则返回0
    cout << cnt << endl;
    for(auto& e : s) cout << e << ' ';
    cout << endl;

    cnt = s.erase(100);
    cout << cnt << endl;
    for(auto& e : s) cout << e << ' ';
    cout << endl;
}

void test_set05()
{
    set<int> s = { 2,3,5,6,7,9 };

    // 1.迭代器。begin()返回第一个元素的迭代器；end()返回最后一个元素的下一个元素的迭代器
    auto it = s.begin();
    while(it != s.end())
    {
        cout << *it << ' ';
        // *it = 999; // err 注意不可修改set内部的元素。因为set容器的元素之间相互关联
        ++it;
    }

    // 2.容量相关
    cout << s.size() << endl;   // 返回容器里的元素个数
    cout << s.empty() << endl;  // 判断容器里是否为空。为空返回true，否则返回false
    s.clear();  // 清空容器
}

void test_map01()
{
    // map<string, int> m;     // 默认构造
    // pair<string, int> p[3] = { {"aaa", 5}, {"bbb", 2}, {"ccc", 1} };
    // map<string, int> m1(p, p + 3);  // 迭代器区间构造

    // map<string, int> m2 = { {"c", 2}, {"b", 1}, {"a", 7} };   // 列表构造

    // for(auto& p : m)
    //     cout << p.first << ' ' << p.second << endl;
    // cout << endl;

    // for(auto& p : m1)
    //     cout << p.first << ' ' << p.second << endl;
    // cout << endl;

    // for(auto& p : m2)
    //     cout << p.first << ' ' << p.second << endl;
    // cout << endl;

    map<int, int, greater<int>> m = { {1,0}, {2,0}, {3,0} };
    for(auto& p : m)
        cout << p.first << ' ' << p.second << endl;
    cout << endl;

    // map<int, int, greater<pair<int,int>>> m = { {1,0}, {2,0}, {3,0} };   // 错误写法
    // 注意是按key比较，而非pair<key, value>
}

void test_map02()
{
    map<string, string> m = { {"left", "左"}, {"right", "右"}, {"sort", "排序"} };
    for(auto& p : m)
        cout << p.first << ' ' << p.second << endl;
    cout << endl;

    auto it = m.find("sort");   // 查找key为sort的元素。找到了返回该元素的迭代器，否则返回m.end()
    cout << it->first << " " << it->second << endl;
    it = m.find("xxx");
}

void test_map03()
{
    map<string, string> m = { {"left", "左"}, {"right", "右"}, {"sort", "排序"} };
    
    // auto it = m.insert({"age", "年龄"});    // m内部元素类型为pair<string,string>，插入的元素类型应当也是pair<string,string>
    // // insert的返回值：
    // // 成功插入返回 pair<指向该元素的迭代器, true>，否则返回pair<指向该元素的迭代器, false>
    // cout << it.first->first << ' ' <<  it.first->second << ' ' << it.second << endl;

    // it = m.insert({"left", "剩余"});    // m中已经有key值为"left"的元素了，这里会插入失败
    // cout << it.first->first << ' ' <<  it.first->second << ' ' << it.second << endl;

    // 1.通过key查找value
    cout << m["left"] << endl;
    cout << m["right"] << endl;
    cout << m["sort"] << endl << endl;

    m["left"] = "剩余"; // 修改value
    cout << m["left"] << endl << endl;

    // 2.充当插入
    m["word"] = "单词"; // 插入{"word", "单词"}。【其实应该是先插入{"word", string()}, 然后再将value修改为"单词”】
    m["who"];       // 没有给value，会用其默认构造，相当于插入{"who", string()}

    for(auto& p : m)
        cout << p.first << ' ' << p.second << endl;
    cout << endl;
}

void test_map04()
{
    map<string, string> m = { {"left", "左"}, {"right", "右"}, {"sort", "排序"} };

    int cnt = m.erase("left"); // 删除key为left的元素。返回成功删除的元素个数，对map而言：成功删除返回1，否则返回0
    cout << cnt << endl;

    for(auto& p : m)
        cout << p.first << ' ' << p.second << endl;
    cout << endl;
}

void test_map05()
{
    map<int, int> m = { {2,3}, {5,6}, {7,9} };  // m存储的元素类型为 pair<int,int>

    // 1.迭代器。begin()返回第一个元素的迭代器；end()返回最后一个元素的下一个元素的迭代器
    auto it = m.begin();
    while(it != m.end())
    {
        cout << it->first << ' ' << it->second << endl;
        // cout << (*it).first << ' ' << (*it).second << endl; // 也可以这样写。it是指向 pair<int,int> 的迭代器

        // it->first = 999;  // err 注意：key不可修改
        ++it;
    }

    // 2.容量相关
    cout << m.size() << endl;   // 返回容器里的元素个数
    cout << m.empty() << endl;  // 判断容器里是否为空。为空返回true，否则返回false
    m.clear();  // 清空容器
}
int main()
{
    test_map05();
    return 0;
}